package integerFactorization;

import java.math.BigInteger;
import java.security.SecureRandom;
import java.util.ArrayList;

import javax.swing.JTextArea;

public class Calculation {
	
	/*Using random generator for c and initial value, returns an arraylist of all factors in number num*/
	protected static ArrayList<BigInteger> polardFactorRandom(BigInteger num,JTextArea con){
		ArrayList<BigInteger> result = new ArrayList<BigInteger>();
		SecureRandom rand = new SecureRandom();
		BigInteger initialValue = new BigInteger(num.bitLength(),rand);
		BigInteger constant = new BigInteger(num.bitLength(),rand);
		con.append("\npolynomial is   X^2 + "+constant+"   and X0 = "+initialValue+"\n"+num+" = ");
		long start = System.nanoTime();
		long end = 0;
		BigInteger counter = BigInteger.ZERO;
		while(true){
			counter = counter.add(BigInteger.ONE);
			BigInteger temp = polard(num, constant, initialValue);
			if(counter.compareTo(BigInteger.ONE) == 0)
				end = System.nanoTime();
			if(temp.compareTo(BigInteger.ONE) == 0){
				result.add(num);
				con.append("("+num+")");
				break;
			}
			if(temp.compareTo(new BigInteger("-1")) == 0) //if one goes in , -1 comes out
				break;
			result.add(temp);
			con.append("("+temp+")");
			num = num.divide(temp);
		}
		con.append("\n");
		con.append("First factor found in "+(end-start)/(1000)+" microseconds ");
		return result;
	}
	
	/*returns an arraylist of all factors in number num*/
	protected static ArrayList<BigInteger> polardFactorPolynomial(BigInteger num, BigInteger constant, BigInteger initialValue, JTextArea con){
		ArrayList<BigInteger> result = new ArrayList<BigInteger>();
		con.append("\npolynomial is   X^2 + "+constant+"   and X0 = "+initialValue+"\n"+num+" = ");
		long start = System.nanoTime();
		long end = 0;
		BigInteger counter = BigInteger.ZERO;
		while(true){
			counter = counter.add(BigInteger.ONE);
			BigInteger temp = polard(num, constant, initialValue);
			if(counter.compareTo(BigInteger.ONE) == 0)
				end = System.nanoTime();
			if(temp.compareTo(BigInteger.ONE) == 0){
				result.add(num);
				con.append("("+num+")");
				break;
			}
			if(temp.compareTo(new BigInteger("-1")) == 0) //if one goes in , -1 comes out
				break;
			result.add(temp);
			con.append("("+temp+")");
			num = num.divide(temp);
		}
		con.append("\n");
		con.append("First factor found in "+(end-start)/(1000)+" microseconds ");
		return result;
	}
	
	/*finds a factor of the given number using polard*/
	private static BigInteger polard(BigInteger num, BigInteger constant, BigInteger initialValue){
		BigInteger x1 = initialValue;
		BigInteger x2 = initialValue;
		BigInteger gcd = new BigInteger("-1");
		if(num.remainder(new BigInteger("2")).compareTo(BigInteger.ZERO) == 0)
			return(new BigInteger("2"));
		for(BigInteger i = BigInteger.ONE; i.compareTo(num) < 0; i = i.add(BigInteger.ONE)){
			x1 = function(x1, constant, num);
			x2 = function(function(x2, constant, num) , constant , num);
			gcd = Calculation.GCD(x2.subtract(x1).abs(), num);
			if(gcd.compareTo(BigInteger.ONE) > 0 && gcd.compareTo(num) < 0)
				break;
		}
		return gcd;
	}
	
	/*using random generators, returns an arraylist of all factors in number num*/
	protected static ArrayList<BigInteger> brentFactorRandom(BigInteger num, JTextArea con){
		ArrayList<BigInteger> result = new ArrayList<BigInteger>();
		SecureRandom rand = new SecureRandom();
		BigInteger initialValue = new BigInteger(num.bitLength(),rand);
		BigInteger constant = new BigInteger(num.bitLength(),rand);
		BigInteger m = new BigInteger(num.bitLength(),rand);
		con.append("\npolynomial is   X^2 + "+constant+"   and X0 = "+initialValue+"   and m = "+m+"\n"+num+" = ");
		long start = System.nanoTime();
		long end = 0;
		BigInteger counter = BigInteger.ZERO;
		while(true){
			counter = counter.add(BigInteger.ONE);
			BigInteger temp = brent(num, constant, initialValue, m);
			if(counter.compareTo(BigInteger.ONE) == 0)
				end = System.nanoTime();
			if(temp.compareTo(BigInteger.ONE) == 0){
				result.add(num);
				con.append("("+num+")");
				break;
			}
			if(temp.compareTo(new BigInteger("-1")) == 0) //if one goes in , -1 comes out
				break;
			result.add(temp);
			con.append("("+temp+")");
			num = num.divide(temp);
			if(num.compareTo(BigInteger.ONE) == 0)
				break;
		}
		con.append("\n");
		con.append("First factor found in "+(end-start)/(1000)+" microseconds ");
		return result;
	}
	
	/*returns an arraylist of all factors in number num*/
	protected static ArrayList<BigInteger> brentFactorPolynomial(BigInteger num, BigInteger constant, BigInteger initialValue, BigInteger m, JTextArea con){
		ArrayList<BigInteger> result = new ArrayList<BigInteger>();
		con.append("\npolynomial is   X^2 + "+constant+"   and X0 = "+initialValue+"   and m = "+m+"\n"+num+" = ");
		long start = System.nanoTime();
		long end = 0;
		BigInteger counter = BigInteger.ZERO;
		while(true){
			counter = counter.add(BigInteger.ONE);
			BigInteger temp = brent(num, constant, initialValue, m);
			if(counter.compareTo(BigInteger.ONE) == 0)
				end = System.nanoTime();
			if(temp.compareTo(BigInteger.ONE) == 0){
				result.add(num);
				con.append("("+num+")");
				break;
			}
			if(temp.compareTo(new BigInteger("-1")) == 0)
				break;
			result.add(temp);
			con.append("("+temp+")");
			num = num.divide(temp);
			if(num.compareTo(BigInteger.ONE) == 0)
				break;
		}
		con.append("\n");
		con.append("First factor found in "+(end-start)/(1000)+" microseconds ");
		return result;
	}
	
	/*finds a factor of the given number using brent*/
	private static BigInteger brent(BigInteger num, BigInteger constant, BigInteger initialValue, BigInteger m){
		BigInteger y = initialValue;
		BigInteger r = BigInteger.ONE;
		BigInteger q = BigInteger.ONE;
		BigInteger gcd = new BigInteger("-1");
		BigInteger x;
		BigInteger k;
		BigInteger ys;
		do{
			x = y;
			for(BigInteger i = BigInteger.ONE; i.compareTo(r) <= 0; i = i.add(BigInteger.ONE))
				y = function(y, constant, num);
			k = BigInteger.ZERO;
			do{
				ys = y;
				for(BigInteger i = BigInteger.ONE; i.compareTo(m.min((r.subtract(k)).abs())) <= 0; i = i.add(BigInteger.ONE)){
					y = function(y, constant, num);
					q = (q.multiply((x.subtract(y)).abs())).mod(num);
				}
				gcd = GCD(q, num);
				k = k.add(m);
			}while(k.compareTo(r) < 0 && gcd.compareTo(BigInteger.ONE) == 0);
			r = r.multiply(new BigInteger("2"));
		}while(gcd.compareTo(BigInteger.ONE) == 0);
		if(gcd.compareTo(num) == 0)
			do{
				ys = function(ys, constant, num);
				gcd = GCD((x.subtract(ys)).abs(), num);
			}while(gcd.compareTo(BigInteger.ONE) == 0);
		return gcd;
	}
	
	/* f(x) = x^2 + c  (mod m)*/
	protected static BigInteger function(BigInteger input, BigInteger constant ,BigInteger mod){
		BigInteger ans = ((input.multiply(input)).add(constant)).remainder(mod);
		return ans;
	}
	
	/* recursive method to calculate GCD of two big integers */
	protected static BigInteger GCD(BigInteger num1, BigInteger num2){
		if(num1.compareTo(BigInteger.ZERO) == 0)
			return num2;
		if(num2.compareTo(BigInteger.ZERO) == 0)
			return num1;
		if(num1.compareTo(num2) == -1)
			return (GCD(num2,num1));
		else
			return (GCD(num2,num1.remainder(num2)));
	}
}
